#include <stdio.h>
#include <stdlib.h>
#include <queue.h>

typedef struct BSTreeNode_	/* a node in the binary search tree - BST */
{
    int val;			/* value of node */
    struct BSTreeNode_ *left;		/* left child of node */
    struct BSTreeNode_ *right;		/* right child of node */
} Node;

void visit(Node *pNode)
{
    if (NULL == pNode)
	return;
    printf("%d ", pNode->val);
}

void levelorder(Node *root)
{
    if (NULL == root)
	return;

    Queue queue;
    queue_init(&queue, NULL);
    queue_enqueue(&queue, root);
    while (queue_size(&queue) != 0) {
	Node *pNode = queue_peek(&queue);
	visit(pNode);
	if (pNode->left != NULL)
	    queue_enqueue(&queue, pNode->left);
	if (pNode->right != NULL)
	    queue_enqueue(&queue, pNode->right);
	queue_dequeue(&queue, (void **)&pNode);
    }
    queue_destroy(&queue);
}



void printByLevel(Node *root)
{
    levelorder(root);
}

int main()
{
    int a[] = {8, 6, 10, 5, 7, 9, 11};
    /* int len = sizeof(a)/sizeof(int); */
    Node bst[7];

    for (int i = 0; i < 7; ++i) {
	bst[i].val = a[i];
	bst[i].left = NULL;
	bst[i].right = NULL;
    }
    
    for (int i = 0; i < 3; ++i) {
	bst[i].left = &bst[2*i + 1];
	bst[i].right = &bst[2*i + 2];
    }

    printByLevel(bst);
    printf("\n");

    exit(0);
}
